关键词: Top-k最短路径, 树分解, Yen算法

Abstract: Based on the principle and property of tree decomposition, this paper converts a graph into a tree structure using a heuristic tree decomposition method. It preprocesses the decomposition tree and stores the index for further Top-k shortest path query. Through the solving of constraint path query in tree decomposition(Top-1 shortest path query) , Top-k algorithm computes the first topk shortest path one by one. It applies tree decomposition method into Yen algorithm. Though Top-k algorithm don’t optimize the worst case time complexity, it can recursively compute the shortest path efficiently through using the stored index. Proved by experiment, Top-k algorithm based on tree decomposition is faster than Yen algorithm, and the size of index is acceptable.


Key words: Top-k shortest path, tree decomposition, Yen algorithm